package com.lsa.iview.ama.count_x_in_sorted_arr;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

import junit.framework.TestCase;

import org.apache.commons.lang.ObjectUtils;

import com.lsa.helpers.Utils;

public class Test extends TestCase {
	Comparator<Integer> c = new Comparator<Integer>(){
		@Override
		public int compare(Integer n1, Integer n2) {
			return n1-n2;
		}
	};
	
	public void testBinarySearch() {
		{
			Integer[] arr = {1,2,3,4,5};
			assertion(1, CountExInSortedArray.binarySearch(arr, 2, c));
		}
		
		{
			Integer[] arr = {1,2,3,4,5,6};
			assertion(1, CountExInSortedArray.binarySearch(arr, 2, c));
		}
		
		{
			Integer[] arr = {11,22,38,444,544,611};
			assertion(3, CountExInSortedArray.binarySearch(arr, 444, c));
		}
		
		{
			Integer[] arr = {11};
			assertion(0, CountExInSortedArray.binarySearch(arr, 11, c));
		}
		
		{
			Integer[] arr = {11,22,38,444,544,611};
			assertion(-5, CountExInSortedArray.binarySearch(arr, 445, c));
		}
	}
	
	public void testCountSortedArr() {
		{
			Integer[] arr = {1,2,3,4,5};
			for (int i = 0; i < arr.length; i++) {
				assertion(1, CountExInSortedArray.count(arr, arr[i], c));
			}
		}
		
		{
			Integer[] arr = {1,2,3,3,3,4,5};
			assertion(3, CountExInSortedArray.count(arr, 3, c));
		}
		
		{
			Integer[] arr = {1,2,3,3,4,5};
			assertion(2, CountExInSortedArray.count(arr, 3, c));
		}
		
		{
			Integer[] arr = {1,1,2,3,4,5};
			assertion(2, CountExInSortedArray.count(arr, 1, c));
		}
		
		{
			Integer[] arr = {1,2,3,4,5,5};
			assertion(2, CountExInSortedArray.count(arr, 5, c));
		}
		
		{
			List<Integer> l = new ArrayList<Integer>();
			for (int i = 0; i < 100; i++) {
				l.add(Utils.random(1, 100));
			}
			
			final int search4ValueCount = 37;
			final int search4Value = 102;
			for (int i = 0; i < search4ValueCount; i++) {
				l.add(search4Value);
			}
			
			for (int i = 0; i < 100; i++) {
				l.add(Utils.random(search4Value+2, 200));
			}
			
			 Integer[] arr = l.toArray(new Integer[0]);
			 Arrays.sort(arr);
			 System.out.println(Arrays.toString(arr));
			 assertion(search4ValueCount, CountExInSortedArray.count(arr, search4Value, c));
		}
		
		{
			Integer[] arr = {11, 1, 2, 3, 5, 6, 7, 7, 9, 9, 12, 15, 15, 16, 17, 17, 17, 17, 18, 20, 21, 21, 24, 24, 27, 27, 28, 29, 30, 33, 34, 34, 34, 38, 38, 39, 41, 43, 43, 44, 45, 45, 45, 46, 46, 48, 48, 48, 48, 49, 49, 52, 55, 55, 56, 56, 56, 58, 58, 59, 59, 60, 61, 62, 62, 62, 64, 65, 66, 67, 67, 69, 71, 71, 72, 73, 74, 76, 77, 79, 79, 80, 81, 82, 83, 84, 84, 85, 90, 91, 92, 92, 92, 93, 94, 95, 96, 96, 97, 99, 102, 102, 102, 102, 102, 102, 102, 102, 102, 102, 102, 102, 102, 102, 102, 102, 102, 102, 102, 102, 102, 102, 102, 102, 102, 102, 102, 102, 102, 102, 102, 102, 102, 102, 102, 102, 102, 104, 105, 106, 109, 110, 110, 112, 114, 116, 116, 118, 118, 118, 119, 119, 123, 123, 126, 127, 127, 127, 127, 128, 128, 129, 133, 133, 134, 134, 135, 136, 137, 140, 141, 141, 144, 144, 148, 148, 149, 150, 152, 153, 154, 155, 156, 158, 158, 159, 161, 161, 161, 167, 167, 167, 169, 169, 170, 170, 170, 171, 172, 172, 172, 174, 175, 176, 176, 176, 178, 178, 179, 180, 180, 181, 181, 181, 182, 182, 183, 184, 184, 184, 186, 186, 186, 187, 190, 191, 192, 192, 192, 193, 193, 194, 196, 196, 198, 199, 200};
			assertion(37, CountExInSortedArray.count(arr, 102, c));
		}
	}
	
	static <T> void assertion(T expected, T actual) {
		assertTrue(String.format("expected %s got %s", expected, actual), ObjectUtils.equals(expected, actual));
	}
}
